package algorthm.systemTraning.dynamicPlanning;
/**
 * @className: Fabonachi
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/3/20 22:00
 */
public class Fabonachi {
    public static void main(String[] args) {
       System.out.println(fabonachi(5));
        System.out.println(fabonachi2(5));
    }

    public static int fabonachi2(int i) {
        int[][] dp = new int[i+1][i+1];
        for(int a = 0 ; a < i+1 ; a++ ){
            for(int b = 0 ; b < i+1 ; b++ ){
                dp[a][b] = -1 ;
            }
        }
        return process(i , dp);
    }

    public static int process(int i , int[][] dp){
        if(i <= 2){
            return 1 ;
        }
        if(dp[i-1][i-2] != -1){
            return dp[i-1][i-2] ;
        }
        int ans = process(i-1 , dp) + process(i-2 , dp);
        dp[i-1][i-2] = ans ;
        return ans ;
    }
    public static int fabonachi3(int i) {
        int[][] dp = new int[i+1][i+1];
        return process2(i,dp);
    }
    public static int process2(int i , int[][] dp){
        return 0 ;
    }

    private static int fabonachi(int i) {
        if(i <= 2){
            return 1 ;
        }
        return fabonachi(i - 1) + fabonachi(i - 2);
    }
}
